package datastructurs.sort;

import java.util.Arrays;

//插入排序
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 2,1, -1, 16,89};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
        insetSort(arr);
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }
    public static void insetSort(int[] arr){
        int insertIndex = 0;
        int insertVal = 0;
        for(int i=0;i<arr.length;i++){
            insertVal = arr[i];
            insertIndex = i-1;
            while(insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            if(insertIndex+1!=i){
                arr[insertIndex+1] = insertVal;
            }
        }
    }
}
